UNR 3 题解
晚上莫名疲惫，开一场 UNR 刺激一下 只有 AC 才能给我麻木的神经带来一丝变态的兴奋
鸽子固定器
将鸽子按 $S$ 从小到大排序。先统计所有长度 $\leq m$ 的连续区间的贡献。
考虑不连续的，选取的一定是一段区间中 $V$ 较大的一些，于是考虑从小到大删除 $V$，删去时用包含它的区间更新答案即可。链表维护。
包含它的每个区间都有恰好 $m$ 个元素，为什么？我好像有点考前 debuff = = 省选 flag $*$ 1 如果没有达到 $m$ 个元素：
- 区间连续：在开头统计过了。
- 区间不连续：间隙中一定有小的被删了！此时加上小的会更优，当前是劣的。
因此删除只会影响到相邻的 $m$ 个区间，$O(nm)$。
To do tree
贪心的选深子树。证明看官方题解吧 /害怕
配对树
考虑树上偶数个点的匹配，树形 dp：子树里的点不可能拿到子树外匹配，所以 $f[x, 0/1]$ 表示 $x$ 子树中有无未匹配点，统计出边的贡献。
其实我们就是统计每条边的贡献。
一条边有贡献当且仅当其两端子树都有奇数个点。相当于统计子树内选点使得偶数长度区间内有奇数个点被选的方案数。即：做前缀和后，$l$ 与 $r$ 奇偶性相同，$pre_l$ 与 $pre_r$ 奇偶性不同。直接做 $O(nm^2)$，线段树维护 $O(nmlogm)$
需要子树信息的题，两种做法：线段树合并，dsu on tree。总共才 $O(n)$ 个点，很难不线段树合并qwq，$[0/1][0/1]$ 分别表示下标和前缀和的奇偶性，$O(nlogn)$。然而其实还可以再优化：$cnt[0/1]$ 表示该区间内下标为偶/奇的位置以前，前缀和为奇的个数。
不懂为什么要 dsu + 线段树？？$O(nlognlogm)$ 又慢又难写
白鸽
噫吁嚱，毒瘤哉！复杂度题真是不好的。
有解：连通且每个点度数为偶数
角度很抽象，不如看作收益，我们要最大化收益。
诡异的收益计算方法题，我们选择费用流。欧拉回路要求每个点入度 = 出度。
考虑一个经典套路就是先每条边随便定向，这样显然不是欧拉回路，那么最大化「给边反向使得每个点入度 = 出度的新收益」即可。
实现细节：角度太炸精度了。有个好东西叫射线法：顺时针经过一条射线的次数 - 逆时针经过的次数。很自然的想法。普通费用流会 T 成 $50$，怎么办？？
这是个单位图！（单位图长什么样？参考二分图 QAQ）好家伙那 dinic 就是 $O((n + m) \sqrt{n})$ 的。
你有办法：多路增广！即，每做完最短路用 dinic 增广残量网络上的余量，题解里说最短路长度不超过 $n^{1/4}$，所以总复杂度就是 $O(n^{3/4} (n + m))$
百鸽笼
放一下以前写的题解：
直接算是错的…（我是 sb！）因为概率不均等，受当前没选完的列数影响。
相当于对于每个 $i$ 求出它最后被选完的方案数。
直接做不好做，考虑类猎人杀做法：容斥，减去存在某个集合 $S$ 在 $i$ 之后被选完的方案数。
因为只关心 $S$ 集合，所以除了 $i$ 和 $S$ 以外的列就不用管了。整个过程概率不变，实际上方案数与 $S$ 种类数 $m$ 和拼成的序列长度 $L$ 有关，
某个 $(m, L)$ 的序列的概率就是 $(\frac{1}{m + 1})^L$。放心大胆 dp，枚举每种数的出现次数。
每次重新 dp 复杂度是 $n^6$。先一个都不选完 dp 一次，再每次改一改就 $n^5$ 了。
省选非正式选手的 xml 是自由的魂灵，由于很喜欢生成函数，打算再补一个 EGF 做法：
每次选择，$a_i$ 会改变，这是不好的。考虑猎人杀怎么做的，认为满了仍然能放，只是没有效果（因为趋于无穷的时候概率和就是 $1$）。
设 $F_i(x) = \sum\limits_{i = 0}^{a_i - 1} \frac{x^i}{i!}$，即没取满的 EGF。假设最后剩下 $k$ 位置，设 $F(x) = \frac{x^{a_k - 1}}{(a_k - 1)!} \prod\limits_{i \neq k} (e^x - F_i(x))$，答案 EGF 即为 $\sum\limits_{i \geq 0} \frac{i! [x^i] F(x)}{n^{i + 1}}$
$\prod$ 是一定要展开的，展开 $F(x)$ 后得到每部分形如 $\lambda e^{dx} x^w$，这部分对答案 EGF 的贡献即为 $\frac{\lambda}{n^{w + 1}} \sum\limits_{i \geq 0} \frac{ (i + w)! d^i }{ i! n^i } = \frac{w! \lambda}{n^{w + 1}} \sum\limits_{i \geq 0} \frac{d^i}{n^i} \binom{w + i}{i}$
设 $\frac{d}{n} = \beta$，$\sum\limits_{i \geq 0} \beta^i \binom{w + i}{i} = \frac{1}{(1 - \beta)^{w + 1}}$，原理就是经典的插板法 QAQ，因此贡献为 $\frac{w! \lambda}{n^{w + 1}} ( \frac{n}{n - d} )^{w + 1}$
设 $V = \max(a_i)$，瓶颈在 dp 预处理系数，$O(n * n * (nV)^2)$（$n$ 个 $k$，转移枚举原来次数和新加次数，$n$ 次转移）
预处理 $\prod (e^x - F_i(x))$，每次除掉 $k$ 的贡献（和第一种做法的“反背包”一样！），$O(n^3 V^2)$。
鸽举选仕
咕